The patent or application file contains at least one drawing executed in color. Copies of this patent or patent application publication with color drawing(s) will be provided by the Office upon request and payment of the necessary fee.
Symmetry is a central concept in many natural and man-made objects and plays an important role in visual perception, design, engineering, and art. Symmetries are often approximate or partial, due to variations in growth processes, imperfections in manufacturing or acquisition procedures, or shortcomings in manual design applications. Several recent efforts in shape analysis have focused on detecting symmetries in two- and three-dimensional shapes. See, for example, J. Podolak et al., A Planar-Reflective Symmetry Transform for 3D Shapes, ACM Trans. Graph. 25, 3, 549-559 (2006) (hereinafter “Podolak”); A. Martinet et al., Accurate Detection of Symmetries in 3D Shapes, ACM Trans. Graph. 25, 2, 439-464 (2006) (hereinafter “Martinet”); and N. J. Mitra et al., Partial and Approximate Symmetry Detection for 3D Geometry, ACM Trans. Graph. 25, 3, 560-568 (2006) (hereinafter “Mitra”). Numerous applications have successfully utilized symmetry information, e.g., for model reduction (see Mitra), scan completion (see S. Thrun et al., Shape from Symmetry, Int. Conference on Computer Vision (2005) (hereinafter “Thrun”)), segmentation (see P. Simari et al., Folding Meshes: Hierarchical Mesh Segmentation Based on Planar Symmetry, Proc. Symposium on Geometry Processing (2006) (hereinafter “Simari”)), shape matching, and viewpoint selection (see Podolak).
Related research has mostly been done in the area of symmetry detection for geometric objects. Early papers focused on detecting exact symmetries in 2D and 3D planar point sets, which limits their applicability for more complex geometries. See, for example, M. Atallah, On Symmetry Detection, IEEE Trans. on Computers, 663-666 (1985); and J. Wolter et al., Optimal Algorithms for Symmetry Detection in Two and Three Dimensions, The Visual Computer, 37-48 (1985). A method for approximate symmetry detection has been proposed by Zabrodsky, defining a symmetry measure for a single given transformation as the distance of a shape to the closest symmetric shape. See H. Zabrodsky et al., Using Bilateral Symmetry to Improve 3D Reconstruction from Image Sequences, Computer Vision and Image Understanding: CVIU 67, 1, 48-57 (1997); and H. Zabrodsky et al., Symmetry as a Continuous Feature, IEEE Transactions on Pattern Analysis and Machine Intelligence 17, 12, 1154-1166 (1995). Martinet finds global symmetries of 3D objects by analyzing the extreme and spherical harmonic coefficients of generalized moments.
There has also been increasing interest in more general symmetry transforms (see Podolak and references therein). For such general symmetry transforms, the goal is to define a continuous measure for all possible transformations of a certain symmetry class. This enables various applications including shape matching, alignment, segmentation or viewpoint selection. Other techniques that analyze distributions in transformation space include the Random Sample Consensus (RANSAC) method (see, e.g., M. A. Fischler et al., Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography, Comm. of the ACM, 381-395 (1981)), as well as geometric hashing techniques that have recently been applied successfully for partial shape matching (see, e.g., H. J. Wolfson et al., Geometric hashing: An overview, IEEE Comput. Sci. Eng. 4, 4, 10-21 (1997); and R. Gal et al., Salient Geometric Features for Partial Shape Matching and Similarity, ACM TOG 25, 1 (2006)). The medial axis transform captures local reflective symmetries with respect to a point, which can be accumulated to extract more global symmetries. See, for example, H. Blum, A Transformation for Extracting Descriptors of Shape, Models for the Perception of Speech and Visual Forms, 362-380 (MIT Press, 1967).
The rather involved computations and the inherent instability of the medial axis transform have prevented a wide-spread use so far. However, recently proposed stable versions of the medial axis transform may potentially alleviate these problems. For an overview, see D. Attali et al., Stability and Computation of the Medial Axis—a State-of-the-Art Report, Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration (2004). Symmetry has also been exploited to define shape descriptors that represent global reflective and rotational symmetries with respect to a shape's center of mass. See, for example, M. M. Kazhdan et al., A Reflective Symmetry Descriptor, ECCV, 642-656 (2002). This approach has been applied successfully for alignment, classification and shape matching. See, for example, M. Kazhdan et al., Symmetry Descriptors and 3D Shape Matching, Sympos. on Geometry Processing, 116-125 (2004). More recent work uses symmetry detection for segmentation (see, e.g., Simari), or scan completion (see, e.g., Thrun).
Various symmetrizations are known in classical geometry, e.g. symmetrization of convex sets (see B. Grunbaum, Measures of Symmetry for Convex Sets, Proc. Symposium Pure Math. 7,233-270 (1963)), or Steiner symmetrization that maps a subset of Euclidean space to a set of spheres, while preserving volume and convexity (see H. Hadwiger, Vorlesungen ueber Inhalt, Oberflaeche und Isoperimetrie, Springer (1957)). Symmetrization methods are also used in function theory (see G. Faber, Ueber potentialtheorie und konforme abbildung, Sitzungsber. Bayer. Akad. Wiss. Math.-Naturwiss. Kl., 49-64 (1920)) and tensor algebra (see A. Schouten, Tensor Analysis for Physicists. (Cambridge Univ. Press. 1951)). None of the aforementioned approaches proposes a method for symmetrization of general geometric shapes.